#!/usr/bin/env python
"""
Minesweeper module.
Enables quick'n'dirty minesweeper lovin'.

Licensed under GPL v2.0, see <URL: http://www.gnu.org>
for full text.

(c) 2005-2006 Pasi Savolainen <pasi.savolainen@iki.fi>
"""

import random

EMPTY, MINE = 0, -1, 
REVEALED = 10

MAX_NEIGH = 8

UNKNOWN, CFLAG, WFLAG, NONEX = -2, -3, -4, -5

PRMAP = { True : { EMPTY: ' ',  MINE: '*', UNKNOWN: '#',
                    CFLAG: 'F', WFLAG: 'f'},
          False : { EMPTY: ' ', MINE: '?', UNKNOWN: '#',
                    CFLAG: 'F', WFLAG: 'F'}}
MN = (-1, 0, 1) # mine neighbourhood
MNI = ((-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1))

class Board:
    def __init__(self, w, h):
        """Initialize Board class to given width and height
        Board is initially EMPTY and flagless.
        """
        self.w = w
        self.h = h
        self.board = [EMPTY for i in range(w*h)]
        self.flags = []

    def at(self, x, y):
        """Return board data at point x,y; or NONEX if board unavailable.
        """
        if (x >= 0 and y >= 0) and (x < self.w and y < self.h):
            return self.board[y*self.w + x];
        return NONEX

    def flag_at(self, x, y):
        """Returns boolean whether there is flag at x,y
        """
        if (x >= 0 and y >= 0) and (x < self.w and y < self.h):            
            return y*self.w+x in self.flags
        return False

    def add_flag(self, x, y):
        """Add flag at x,y
        """
        if self.flag_at(x, y) == False:
            self.flags.append(y*self.w+x)

    def remove_flag(self, x, y):
        """Remove flag from x,y
        """
        self.flags.remove(y*self.w+x)
    
    def toggle_flag(self, x, y):
        """Toggle flag status at x,y
        """
        if self.flag_at(x, y):
            self.remove_flag(x, y)
        else:
            self.add_flag(x, y)        

    def line_done(self, line=-1):
        """Check if line is considered done.
        Line is done if all tiles are either marked with flag or
        revealed.
        'line' -parameter optionally directs to check line at given index.
        """
        if line == -1:
            line = self.h-1
        # print self.board[line*self.w:(line+1)*self.w]
        for x in range(self.w):
            if self.flag_at(x, line) == True:
                # user has marked
                pass
            elif self.at(x, line) < REVEALED :
                # hasn't marked, and is not revealed.
                return False
        # all were marked or revealed.
        return True

    def populate_area(self, y1, y2, mines):
        """Populate area in lines y1-y2 with 'mines' number of mines.
        """        
        for i in range(mines):
            while 1:
                x, y = random.randint(0, self.w-1), random.randint(y1, y2)
                if self.at(x, y) == MINE:
                    continue
                self.add_mine(x, y)
                break

    def remove_bottom_line(self):
        """Remove bottom line of board.
        Returns tuple of (correct_flags, total_flags, mines_in_line, raw_line)
        """        
        y = self.h-1 # index to last line
        cflags, flags, mines = (0, 0, 0)
        bl = self.board[y*self.w:(y+1)*self.w] # save last line
        # go throught width number of tiles.
        for x in range(self.w):
            v = self.at(x, y)
            if self.flag_at(x, y):
                flags += 1
                if v == MINE: # correct flag
                    cflags += 1
            if v == MINE:
                mines += 1
                self.remove_mine(x, y, REVEALED)
        # pad board with empty values at start
        self.board = [EMPTY for i in range(self.w)] + self.board[0:y*self.w]
        # top line has incorrect mine counts.
        for x in range(self.w):
            self.set(x, 0, self.recalc_mines(x, 0))
        # correct flag indexes to point one line lower
        self.flags = map(lambda x: x+self.w, self.flags)
        # filter out flags with indices pointing too far.
        self.flags = filter(lambda x: x < self.w*self.h, self.flags)
        #lr = self.getset_line_revelable(self.h);
        #if len(lr):
            # print "lr:", lr
        #    self.reveal(0,0,lr)
        # print "mines", mines
        return (cflags, flags, mines, bl)

    
    def mines_count(self):
        return len(filter(lambda x: x==MINE, self.board))

    def recalc_mines(self, x, y):
        """Return number of neighbouring mines at point x,y
        """
        mines = 0
        for i in MN:
            for j in MN:
                #print self.at(x+i, y+j),
                if (i or j) and (self.at(x+i, y+j) == MINE):
                    mines += 1
            #print "tot:", mines
        return mines
    
    def get_minecounts(self, y):
        return [self.recalc_mines(x, y) for x in range(self.w)]
    
    def get_covered(self):
        covered = []
        for count in xrange(self.w*self.h):
            if ((count not in self.flags) and
                (MINE <= self.board[count] < REVEALED)):
                covered.append((count%self.w, count/self.w))
        return covered
                    
    def increase(self, x, y):
        """Increase count of neighbouring mines at point x,y
        Does not check neighbouring mines.
        """
        co = self.at(x, y)
        if co >= EMPTY:
            self.set(x, y, co+1)
            
    def decrease(self, x, y):
        """Decrease count of neighbouring mines at x,y
        See .increase()
        """
        co = self.at(x, y)
        if co > REVEALED or (EMPTY < co < REVEALED):
            self.set(x, y, co-1)
        
    def add_mine(self, x, y):
        """Add mine at x,y
        """
        self.set(x, y, MINE);
        for i in MN:
            for j in MN:
                self.increase(x+j, y+i)
                
    def remove_mine(self, x, y, rev = EMPTY):
        """Remove mine at x,y
        """
        for i in MN:
            for j in MN:
                self.decrease(x+j, y+i)
        self.set(x, y, rev+self.recalc_mines(x, y));

    def surroundings(self, x, y):
        """Return coordinates that represent surroundings of (x,y).
           Will include only legal coordinates. includes (x,y)
        """
        ret = []
        for i in MN:
            for j in MN:
                v, w = x+i, y+j
                if (v >= 0 and w >= 0) and (v < self.w and w < self.h):
                    ret.append((x,y))
        return ret

    def set(self, x, y, t):
        """Set board data at x,y to t
        """
        if ((x >= 0 and y >= 0) and
            (x < self.w and y < self.h)):
            self.board[x+y*self.w] = t
        else:
            raise "Bad data: %s,%s %s" % (x, y, t)

    def reveal_single(self, x, y):
        """Reveal single tile from board
        """
        if self.flag_at(x,y):
            return 0
        
        content = self.at(x, y)
        if content == MINE:
            return 1
        if EMPTY <= content < REVEALED:
            self.set(x, y, content+REVEALED)
        return 0

    def get_revelable(self, x, y):
        """Get revelable tiles from around x,y
        Content can be revealed if it's not mine and isn't
        already revealed, eg. EMPTY or 1 <= x <= 8
        """
        revel = []
        for i, j in MNI:
            content = self.at(x+j, y+i)
            if content >= 0 and content < REVEALED and not self.flag_at(x, y):
                # print "revelable:", x+i, y+j
                revel.append(x+j+(y+i)*self.w);
        return revel
    
    def getset_line_revelable(self, y):
        revel = []
        ll = self.get_minecounts(y)
        for x in range(self.w):
            if ll[x] == 0:
                revel.append(x+(y-1)*self.w)
        return revel
    
    def smart_reveal(self, x, y):
        """Smartly reveal from x, y.
        If minecount at x,y matches number of mines marked in x,y surroundings,
        reveal all unrevealed tiles.
        """
        nmines = self.recalc_mines(x, y)
        mmarked = 0
        for i, j in MNI:
            if self.flag_at(x+i, y+j):
                mmarked += 1
        blown, visited = [], []
        # print "n/m", mmarked, nmines
        if nmines == mmarked:            
            for i, j in MNI:
                if self.flag_at(x+i, y+j) == False:
                    bl, vis = self.reveal(x+i, y+j, [], False)
                    blown += bl
                    visited += vis
        else:
            #print "cannot reveal, markings missing"
            pass
            
        return (blown, visited)
                    
    def reveal(self, x, y, queue=[], smart_reveal=True):
        """Iteratively reveal board from point x,y
        """
        if len(queue) == 0:
            if self.at(x, y) >= REVEALED and smart_reveal:
                # As this is a 'click' on already revealed tile, try smart
                # revealing that will uncover areas that are not marked as
                # mine.
                return self.smart_reveal(x, y)
            elif (0 <= x < self.w) and (0 <= y < self.h):
                queue = [x+y*self.w]
            else: return ([], [])
        blown, visited = [], []
        while queue:
            # print "q:", queue
            at = queue.pop()
            x, y = at % self.w, at/self.w
            # print (x, y, at) ,
            content = self.at(x, y)
            if content == NONEX:
                continue
            if content == EMPTY:
                rev = self.get_revelable(x, y)
                for i in rev:
                    if i not in queue:
                        queue.append(i)
            if not self.revelable(x, y):
                continue
            if self.reveal_single(x, y):
                blown.append((x, y))
            else:
                visited.append((x, y))
        return (blown, visited)
    
    def revelable(self, x, y):
        content = self.at(x, y)
        if (content >= 0 and content < REVEALED) or content == MINE:
            return True
        return False
    
    def us_char(self, x, y):
        if self.flag_at(x, y):
            return CFLAG
        content = self.at(x, y)
        if content >= REVEALED:
            return content-REVEALED
        return UNKNOWN

    def pr_char(self, x, y, internal=False):
        """ printable character of (x,y)
        """
        chmap = PRMAP[internal]
        content = self.at(x, y)
        # onko lippua paikalla    
        if self.flag_at(x, y):
            # onko ihan oikea lippu
            if content == MINE:
                return chmap[CFLAG]
            else: return chmap[WFLAG]
        if content < REVEALED:
            if internal:
                if content == MINE:
                    return chmap[MINE]
                return "%d" % content
            else: return chmap[UNKNOWN]
        if content in [REVEALED]:
            return chmap[EMPTY]
        return "%d" % (content-REVEALED)

    def pprint(self, internal=False):
        """Prettyprint board
        """
        numb = "0123456789abcdef"*16
        print "   "+numb[0:self.w]
        print "  +" + "-"*self.w
        for y in range(self.h):
            out = []
            for x in range(self.w):
                out.append(self.pr_char(x, y, internal))
            print ("%02.0d|" % y)+"".join(out)

### Testing. python exsheep.py
            
def main():
    mines = ((0, 0), (0, 1), (2, 0), (2, 2), (5, 5))
    b = Board(10, 10)
    b.pprint()
    # b.reveal(1, 1)
    for i in mines:
        b.add_mine(*i)
    b.pprint(True)
    b.pprint()
    b.reveal(4, 0)
    

if __name__ == '__main__':
    main()

# rm -rf /
# It's funny, laugh.
